perm filename T3.LST[144,DBL] blob
sn#026391 filedate 1973-02-26 generic text, type T, neo UTF8
MIXAL - MIX Assembly Language
26-FEB-1973 16:42
0000 + 0000000024 BLANKS ORIG *+24 ;These locs. should always be blank.
0024 + 0000000000 N CON 0 ;The number of nodes
0025 + 0000000049 TPL ORIG *+24 ;The desired total path length
0049 + 0000000000 LOG CON 0 ;A sequential linear list, whose i th element
* is Floor(log(i)), where log ≡ (log to base 2).
0050 + 0000000550 ORIG *+500 ;I have assumed that n will never be > 500.
0550 + 0000000000 S CON 0 ;A sequential linear list whose i th element
* is the sum of elements 1 to i of LOG.
0551 + 0000001051 ORIG *+500
1051 + 0000001551 ORIG *+500
1551 + 0000002051 LOOKUP ORIG *+500
2051 + 0000002551 BAL ORIG *+500
+ 0000003500 ZEROS EQU 3500 ;An area which remains as zeros.
+ 0000000009 VISIT EQU 1:1 ;The field spec. indicating whether or not wehave visited this no2551 + 0000003351 BUFFER ORIG *+800 ;This should be ample to hold a finaltree traversal encoding.
3351 + 0000000000 DIFF CON 0 ;Holds the difference between the pure balanced+
* tail tree path length, and the desired TPL.
3352 + 0000000000 XOLD CON 0 ;Holds the previous path length, in case we went too far.
3353 + 0000000000 K CON 0 ;Holds the number of nodes in the balanced part oftree.
3354 + 00 00 00 15 00 TITLE ALF N
3355 + 00 00 23 17 13 ALF TPL
3356 + 00 00 00 00 00 ALF
3357 + 00 00 00 00 00 ALF
3358 + 00 00 00 00 00 ALF
3359 + 04 16 24 07 00 ALF Doug
3360 + 13 05 15 01 23 ALF Lenat
3361 + 00 00 00 00 00 ALF
3362 + 03 22 00 31 34 ALF CS 14
3363 + 34 01 00 00 17 ALF 4A P
3364 + 19 16 02 13 05 ALF roble
3365 + 14 00 00 34 00 ALF m 4
3366 + 00 00 00 00 00 ALF
3367 + 23 16 23 01 13 ALF Total
3368 + 00 17 01 23 08 ALF Path
3369 + 00 13 05 15 07 ALF Leng
3370 + 23 08 00 09 15 ALF th in
3371 + 00 02 09 15 01 ALF Bina
3372 + 19 28 00 23 19 ALF ry Tr
3373 + 05 05 22 00 00 ALF ees
3374 + 0000003379 ORIG *+5
+ 0000000036 RSON EQU 4:4 ;Field in a TREE node pointing to right son.
+ 0000000045 LSON EQU 5:5 ;Field specification pointing to the left son.
* note that this restricts n to be under 65; a trivial modification
* will allow n to range up to 500.If n is requested over 2000, a
* total revision of the program would be necessary.
+ 0000000037 SONS EQU 4:5 ;Field which is blank iff the node is a leaf.
+ 0000000027 FATHER EQU 3:3 ;Field spec. pointing to the node's parent.
+ 0000000036 FIELD EQU 4:4 ;Field spec. for the field byte of a MIX instruction.
+ 0000000042 LPAREN EQU 42
+ 0000000043 RPAREN EQU 43
+ 0000000046 STAR EQU 46
+ 0000000016 READER EQU 16
+ 0000000018 PRINTER EQU 18
*
*
3379 + 0000 00 18 37 CONTINU OUT BLANKS(PRINTER)
3380 + 0000 00 18 37 OUT BLANKS(PRINTER)
3381 + 0024 00 16 36 START IN N(READER) ;Read n. We are permitted the inefficiency of
3382 + 3382 00 16 34 JBUS *(READER) ;JBUS instructions. See Knuth and
* my earlier programs for examples
* of more efficient I/O.
3383 + 0024 00 05 15 LDX N
3384 + 3386 00 04 47 JXNZ *+2 ;Are we finished the final problem in the run??
3385 + 0000 00 02 05 HLT ; yes; so we halt.
3386 + 3354 00 18 37 OUT TITLE(PRINTER) ; Here we
* write out a title line.
3387 + 0024 00 18 37 OUT N(PRINTER) ;We write n and tpl
3388 + 3388 00 18 34 JBUS *(PRINTER) ; while they are still in char. form.
3389 + 0000 00 02 48 ENTA 0
3390 + 0000 00 00 05 NUM
3391 + 0024 00 05 24 STA N ; re-store the numeric value of n.
3392 + 0025 00 05 15 LDX TPL ;Convert TPL from char. code to numeric.
3393 + 0000 00 02 48 ENTA 0
3394 + 0000 00 00 05 NUM
3395 + 0025 00 05 24 STA TPL
3396 ↓ - 0001 00 02 49 ENT1 TREE
3397 + 0024 00 05 10 LD2 N
3398 + 3399 00 36 26 ST2 *+1(FIELD)
3399 + 3500 00 01 07 MOVE ZEROS ;WARNING: INSTRUCTION MODIFICATION HERE.
*
*
* The following loop sets up the first n entries in LOG and in S:
*
3400 + 0000 00 02 49 ENT1 0 ;rI1 holds the exponent of the current power of 2.
3401 + 0000 00 02 50 ENT2 0 ;rI2 holds the sum of all previous terms.
3402 + 0001 00 02 51 ENT3 1 ;rI3 holds 2 to the current power( 2 ↑ <rI1> ).
3403 + 0000 00 02 52 ENT4 0 ;rI4 stops us when n terms have been computed.
3404 + 0001 00 02 48 ENTA 1 ;rA tells us when to increase the terms of LOG.
*
3405 ↓ - 0001 00 00 39 JMP LOOP1 ;A standard programming trick, saving n-1 tyme units.
3406 + 0000 03 00 51 SKIP1 INC3 0,3 ;Double rI3; i.e, increaase its log by 1.
3407 + 0000 03 02 48 ENTA 0,3 ;rA tells us when to increase the terms of LOG.
3408 + 0001 00 00 49 INC1 1
3409 ← + 0000 01 00 50 LOOP1 INC2 0,1
3410 + 0001 00 00 52 INC4 1
3411 + 0550 04 05 26 ST2 S,4
3412 + 0049 04 05 25 ST1 LOG,4
3413 + 0001 00 01 48 DECA 1
3414 + 3409 00 02 40 JAP LOOP1
3415 + 0024 00 05 60 CMP4 N
3416 + 3406 00 09 39 JLE SKIP1
*
*
*
*
* This loop is the "guts" of the program: we determine how many nodes
* are in the balanced section, and how many are in the tail.
*
3417 + 0000 00 02 51 ENT3 0 ;rI3 holds the L*(L+1)/2 term.
3418 + 0024 00 05 13 LD5 N ;rI5 holds K, the number of nodes in the balanced part.
3419 - 0001 00 02 54 ENT6 -1 ;rI6 holds L, the number of nodes in the tail.
3420 + 0000 06 01 53 DEC5 0,6 ;K must always remain equal to N - L.
3421 + 0001 00 00 54 LOOP2 INC6 1
3422 + 0001 00 01 53 DEC5 1
3423 + 0000 06 00 51 INC3 0,6 ;Update this term.
3424 + 3352 00 05 24 STA XOLD
3425 + 0000 06 02 48 ENTA 0,6 ;Get the L * Floor(log(k)) term.
3426 + 0049 05 05 03 MUL LOG,5
3427 + 0005 00 02 06 SLAX 5
3428 + 0000 03 00 48 INCA 0,3 ;The accumulator now contains the sum of terms 1,2.
3429 + 0550 05 05 01 ADD S,5 ;We add in the sum of LOGs from 1 to K: the final term.
3430 + 0025 00 05 56 CMPA TPL ;See if we have gone far enough....
3431 + 3421 00 04 39 JL LOOP2 ; we haven't; go back and try again.
* WE HAVE SUCCEEDED !!!
*
3432 + 0025 00 05 08 LDA TPL
3433 + 3352 00 05 02 SUB XOLD
3434 + 3351 00 05 24 STA DIFF
3435 + 0001 00 00 53 INC5 1
3436 + 0001 00 01 54 DEC6 1
3437 + 0000 05 02 50 ENT2 0,5
*
*
*
3438 + 3353 00 05 29 ST5 K
3439 + 0049 25 05 12 LD4 LOG,K
3440 + 0001 00 00 52 INC4 1
3441 + 0042 00 02 48 ENTA LPAREN
3442 + 0043 00 02 55 ENTX RPAREN
3443 + 0046 00 02 50 ENT2 STAR
3444 + 2055 00 02 49 ENT1 BAL+4
3445 + 0000 00 02 52 ENT4 0
*
3446 + 0024 00 05 19 LD3N N
3447 + 2051 03 05 24 LOOP8 STA BAL,3
3448 + 0001 00 00 51 INC3 1
3449 + 3447 00 00 43 J3N LOOP8
*
3450 + 0002 00 02 51 ENT3 2
*
3451 + 2051 03 05 31 LOOP9 STX BAL,3
3452 + 2052 03 05 26 ST2 BAL+1,3
3453 + 1551 04 05 27 ST3 LOOKUP,4
3454 + 2053 03 05 24 STA BAL+2,3
3455 + 3456 00 36 27 ST3 *+1(FIELD)
3456 + 2051 04 01 07 MOVE BAL,4
3457 + 0005 03 00 51 INC3 5,3
3458 + 0001 00 01 52 DEC4 1
3459 + 0001 00 01 52 DEC4 1
3460 + 3451 00 02 44 J4P LOOP9
*
3461 + 0000 00 02 52 ENT4 0
3462 + 0048 05 05 11 LD3 LOG-1,5
3463 + 0000 06 00 51 INC3 0,6
*
3464 + 2551 04 05 24 LOOP10 STA BUFFER,4
3465 + 0001 00 00 52 INC4 1
3466 + 0001 00 01 51 DEC3 1
3467 + 3464 00 02 43 J3P LOOP10
*
3468 + 3351 00 05 17 LD1N DIFF
3469 + 0000 06 00 49 INC1 0,6
3470 + 0001 06 02 51 ENT3 1,6
*
3471 + 2551 04 05 26 LOOP11 ST2 BUFFER,4
3472 + 2552 04 05 31 STX BUFFER+1,4
3473 + 0002 00 00 52 INC4 2
3474 ↓ - 0001 00 04 41 J1NZ L11B
3475 + 2551 04 05 26 ST2 BUFFER,4
3476 + 2552 04 05 24 STA BUFFER+1,4
3477 + 2553 04 05 26 ST2 BUFFER+2,4
3478 + 2554 04 05 31 STX BUFFER+3,4
3479 + 2555 04 05 31 STX BUFFER+4,4
3480 + 0005 00 00 52 INC4 5
3481 ← + 0001 00 01 49 L11B DEC1 1
3482 + 0001 00 01 51 DEC3 1
3483 + 3471 00 03 43 J3NN LOOP11
*
3484 + 3353 00 05 22 LD6N K
3485 + 1551 06 05 09 LD1 LOOKUP,6
3486 - 0006 01 02 53 ENT5 -6,1
3487 + 2551 04 02 49 ENT1 BUFFER,4
3488 + 3489 00 36 29 ST5 *+1(FIELD)
3489 + 2058 00 01 07 MOVE BAL+7
3490 + 0000 05 00 52 INC4 0,5
3491 + 0024 00 05 13 LD5 N
3492 + 0048 05 05 13 LD5 LOG-1,5
3493 + 0002 00 01 53 DEC5 2
3494 + 2551 04 05 31 LOOP12 STX BUFFER,4
3495 + 0001 00 00 52 INC4 1
3496 + 0001 00 01 53 DEC5 1
3497 + 3494 00 02 45 J5P LOOP12
*
* Here we do the actual printing of the encoded traversal
*
3498 + 0000 00 02 51 ENT3 0
3499 + 2551 03 18 37 LOOP13 OUT BUFFER,3(PRINTER)
3500 + 0024 00 00 51 INC3 24
3501 + 0024 00 01 52 DEC4 24
3502 + 3499 00 03 44 J4NN LOOP13
*
* Go back and read in a new request
*
3503 + 3379 00 00 39 JMP CONTINU ;This differs from START only in the printing out of 2 blank line *
3504 + 000000 3381 END START
SYMBOL TABLE
BLANKS +0
N +24
TPL +25
LOG +49
S +550
LOOKUP +1551
BAL +2051
ZEROS +3500
VISIT +9
BUFFER +2551
DIFF +3351
XOLD +3352
K +3353
TITLE +3354
RSON +36
LSON +45
SONS +37
FATHER +27
FIELD +36
LPAREN +42
RPAREN +43
STAR +46
READER +16
PRINTER +18
CONTINU +3379
START +3381
3504 ← + 0000000000 TREE +3504 (3396)
LOOP1 +3409 (3405)
SKIP1 +3406
LOOP2 +3421
LOOP8 +3447
LOOP9 +3451
LOOP10 +3464
LOOP11 +3471
L11B +3481 (3474)
LOOP12 +3494
LOOP13 +3499